{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 感知机Perceporn\n",
    "\n",
    "> 理论 统计学习方法\n",
    "> \n",
    "> 代码 numpy version && torch version"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 模型\n",
    "二分类的线性分类模型，目的是找到一个超平面将所有实例**线性划分**为正例和负例，取值为$+1 -1$。属于是判别模型\n",
    "\n",
    "输入空间到输出空间由以下函数进行定义\n",
    "$$\n",
    "f(x) = sign(w\\cdot x + b)\n",
    "$$\n",
    "\n",
    "感知机是在特征空间中所有线性分类模型的集合（因为分离超平面不唯一）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 策略\n",
    "\n",
    "首先要求数据集线性可分，采用基于误分类点的损失，采用梯度下降法对损失函数进行极小化。\n",
    "\n",
    "对于误分类的点，总是有$-y_i(w\\cdot x_i + b) > 0$成立，该式子再乘上一个$1\\over ||w||$就是误分类点到超平面的距离\n",
    "\n",
    "将所有的误分类点到分离超平面的距离进行加总，然后不考虑前面的L2范数，就得到了感知机的损失函数\n",
    "$$\n",
    "Loss(w,b) =  - \\Sigma_{x_i\\in M} y_i(w\\cdot x_i + b),M是误分类点集合\n",
    "$$\n",
    "\n",
    "Loss是非负的，因为没有误分类点Loss=0,误分类点越少，Loss越小。Loss是连续可导的。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 算法\n",
    "\n",
    "SGD\n",
    "\n",
    "1. 原始形式\n",
    "   \n",
    "   求解$\\min Loss(w,b)$，每一次随机选择一个误分类点来修正w,b。\n",
    "   Loss关于w,b的梯度分别为\n",
    "   $$\n",
    "      \\Delta_w Loss(w,b) = - \\Sigma y_i x_i\n",
    "      \\\\\n",
    "      \\Delta_b Loss(w,b) = - \\Sigma y_i\n",
    "   $$\n",
    "   给定一个学习率$\\eta$，对w,b进行更新，对每个误分类点(也就是有 $ y_i (w\\cdot x_i + b)\\le 0$成立)\n",
    "   $$\n",
    "      w = w + \\eta y_i x_i\n",
    "      \\\\\n",
    "      b = b + \\eta y_i\n",
    "   $$\n",
    "   迭代Loss不断减少，直到为0，则找到了一个分离超平面   \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "w is [3. 3.],b is 1\n",
      "w is [2. 2.],b is 0\n",
      "w is [1. 1.],b is -1\n",
      "w is [0. 0.],b is -2\n",
      "w is [3. 3.],b is -1\n",
      "w is [2. 2.],b is -2\n",
      "w is [1. 1.],b is -3\n",
      "finally get w is [1. 1.],b is -3\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "x_train = np.array([[3,3],[4,3],[1,1]])\n",
    "y_train = np.array([1,1,-1])\n",
    "\n",
    "# 定义超参\n",
    "lr = 1\n",
    "w = np.zeros(2)\n",
    "b = 0\n",
    "\n",
    "def sign(x):\n",
    "    if x>0:\n",
    "        return 1\n",
    "    else:\n",
    "        return -1\n",
    "\n",
    "flag = True\n",
    "while flag:\n",
    "    label = np.zeros_like(y_train)\n",
    "    for i,v in enumerate(x_train):\n",
    "        y_hat = (v*w).sum() + b\n",
    "        if sign(y_hat) != y_train[i]:\n",
    "            w = w + lr * v * y_train[i]\n",
    "            b = b + lr * y_train[i]\n",
    "            print(\"w is {},b is {}\".format(w,b))\n",
    "        label[i] = sign(y_hat)\n",
    "    if (label == y_train).all():\n",
    "        flag = False\n",
    "\n",
    "print(\"finally get w is {},b is {}\".format(w,b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAOYAAADdCAYAAACv1w7VAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAAJ1wAACdcBsW4XtwAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAATE0lEQVR4nO3deZAW9Z3H8feXUElNluAR5BjkcrhRboZh8BYNDEYjMWJEruHwjHKooELilapUrbtbZdxEExw8MoBcouCY3egmRoGo6DCAYKIhbpSRlSAeoxPl+O4f/TzMgIAw/czT/TzP51Vl6TMD3d8S3vy6m36eNndHROKlSdQDiMiXKUyRGFKYIjGkMEViSGGKxFDTdO2oW7duXlBQkK7diWSEZ5555s/u3v3gr6ctzIKCAioqKtK1O5GMYGZbD/V1HcqKxJDCFIkhhSkSQwpTJIZCh2lmXc1st5kVpWIgEUnNijkXeD7sRnQzvUidUGGaWSGwHXg3zHb+uXsvY+a9xMqq6jCbEckaYVfMOcDPDvdNMxtjZhVmVlFdffjovtG0Cd1bN+fGRZU8pThFGn6DgZmNBNa5+04zO+SPcfdyoBygpKTksMeqZsbcC3tgBtMWVeLuXNy3bUNHE8l4Ye786QucbWbFwGlANzMb5e7vNWRjZsackT0AmP74egDFKTmrwWG6+0+BnwKY2cPAAw2NMikZp6E4Jbel5F5Zd5+Qiu1AEOft9VZOd/heP8UpuSVtN7Efi2ScZjBj8Xoc55J+J0c9lkjaxDJMCOK8raQHZsbMxVUAilNyRmzDhCDOW0d0x4AZi6twh1H9Fadkv1iHCUGcs0cE7yOduSRYORWnZLvYhwn14jTFKbkhI8KERJzD61ZOd/j+AMUp2SljwoS6OA3jpqVVOHCp4pQslFFhQhDnrOHdMIOblwaHtYpTsk3GhQlBnLd8pxtNEnG6Oz8Y2C7qsURSJiPDhCDOmy7oBsAtyzbgwGWKU7JExoYJdXEaxqxlG8DhskGKUzJfRocJQZwzL+iKGcxavgFQnJL5Mj5MCOKccX5XDMUp2SErwoQgzunndwWS55zO6EHtI55KpGGyJkyoF6cZs5ZtxB0uL1ScknmyKkxIxDmsCwCzl2/EgR8qTskwWRcmHHjOeevyYOW8YrDilMyRlWEmJc85b3tiI44zZnCHiCcSOTpZHSbUxXn7E5sAFKdkhKwPE4I4zYI43eHKIsUp8ZYTYQJMG9YVw5izYhMOjFWcEmM5EybAjcO6YAZzV2wCd8YO6Rj1SCKHlFNhAtxwXhcMmPvk6wCKU2Ip58IE+NF5wd9zzn3ydRwYpzglZnIyTAjiNIMfJ1ZOxSlxkrNhAlx/bhfMjB8/+TruML64Y9QjiQA5HibAded0BuAnT72OuzNhaKeIJxJRmEAQpxncsXIzgOKUyIUK08w6AguA3YltXePuG8KPlX7Xnh2snHes3IwDExVn5qipgbIyWL0ahg6F0lJo1iyz53H3Bv9DEGOTxH+fCyw63I8dMWKEZ4Jf/P4t7zBrlZe9uDXqUeRofPKJe+fO7nl57hD8u3Pn4OsZMA9Q4YfoJdSj3t19j7vvS7xsDlSF2V4cXHN2AbOGd+fOlZspe/FvUY8jX6WsDLZtg9ra4HVtbfC6rCyj5wkVJoCZ9TWztcD9wHMHfW+MmVWYWUV1dXXYXaXNNWcXMHtEd+5atZmHFGe8rV5dF0FSbS2sWZPR84QO093Xu/sQ4CKCOOt/r9zdS9y9JD8/P+yu0urqswq4dUR37l61mXkvbI16HDmcoUMhL+/Ar+XlQXFxRs8TKkwz+0a9lx8Bn4XZXtxcdVYBt5V0556ntyjOuCothbZt62LIywtel5Zm9Dxh/7pkqJndAeyF4DGWIbcXO1PPLMAw7nl6CwCTzzgl4onkAM2aQWVlcA63Zk2wMkV5VTZF81hwYajxlZSUeEVFRVr21RjmvbCVe57ewu0lPZhypuKU1DCzZ9y95OCv6waDo5RcKe95eguOM/XMgognkmymMI/BAXF6cA4q0hgU5jGafMYpmBl3rwpu31Oc0hgUZgNMOj24Xe/uVcHte1crTkkxhdlA9eMExSmppTBDmHR6Jwy4a9Vm3IM7hkRSQWGGVHp6J8zgzpWbcXz/u1REwlCYKZB8i9idK4OVM/nma5GGUpgpMnFocFibfLO14pQwFGYKTRjaCTPjJ08FH/ClOKWhFGaKjS/uuP/T99yd68/tEvVIkoEUZiMYN6Tj/g+Vdq/7HFuRo6UwG0nyE96THyp9g+KUY6AwG9HYIR3BLHhWCopTjp7CbGRjizpgEDxlzIMHG4l8FYWZBsnncQaPAHSmDesa8UQSdwozTa4s6nDAw3OTT7oWORSFmUZjBnfAMG57YiOgOOXwFGaaXTG4PYDilCNSmBG4YnB7zODW5RtxYPqw4KljIkkKMyI/LGyPAbOXbwR3pp/fVXHKfgozQpcXBoe1sxMr5wzFKQkKM2KXFwaHtbOWbcQdZl6gOEVhxsLoQXUrJyhOUZixMXpQewxj1vINOM5NF3RTnDlMYcbIZYPaATBrefDsX8WZuxRmzFw2qB0YzFq2AXe4+TuKMxeFfdR7L+BBYB+wB5js7nosVkiXDWyHAbcs24ADtyjOnBN2xdwBjHT3j8xsODAXmBh+LPnBwHaYGTcvrcIdZg1XnLkkVJju/n69l7sJVk1JkUsHnAzAzUurAMWZS1JyjmlmecCdwJRUbE/qXDrgZAy4aWkVjjN7eHfFmQNCh2lmTYFFwL3uvuWg740BxgD06dMn7K5y1vcHnIwZzFxSBQ6zRyjObBf24o8B84HfuvuKg7/v7uVAOQQPrg2zr1w3qn9wWDtzSRUO3Ko4s1rYFXMk8H2gnZmNBta7+7TwY8mhjOqfWDkXV+Hu3FbSQ3FmqbAXf1YB30zRLHIULumXWDkXBxeEFGd20g0GGeiSfidjGDMWr8cdbh+pOLONwsxQ3+vXFjOY/vh6QHFmG4WZwS7u2xYI4nRgjuLMGgozwx0Qp8PcCxVnNlCYWeDAldP58YU9FWeGU5hZ4uK+bTEzpi2qBFCcGU5hZpGL+uRjwLTEYe1Pvqs4M5XCzDLf7ZMPBHGC4sxUCjMLfbdPPmZw4yLFmakUZpa6sHc+hnHDokrcnTsu6qU4M4jCzGIje7cBCOIE7lScGUNhZrn6cYLizBQKMweM7N0GM/jRwkrc4a6LFWfcKcwcUXJaGwy4fmEljnPXRafSpInijCuFmUNGnNaG+6lbOe++WHHGlcLMMSNOa8P9BtcvCM45FWc8NYl6AEm/4ae24f4r+vP4K+8w58lN7NunT32JG4WZo4af2pr7r+jP4lfe4fYVijNuFGYOS8a5ZN073L5io+KMEYWZ44af2pr/HNOfJeveVZwxojCF7/RqzS/G9Gfpq+9y2xOKMw4UpgBwQa/W/GLMAJa9pjjjQGHKfuf3bMUvFWcsKEw5wLB6cd66XHFGRWHKlyTjXF75LrOXb1CcEVCYckjDerbigSsHsKKyWnFGQGHKYZ3XoxW/vLI/KyqrmbVMcaaTwpQjOq9HKx4Y258n11dzy7IN7FWcaREqTDP7ppmtNbMPzezyVA0lB6r5oob7XrqP0UtGc99L91HzRU1a939u91Y8OHYAT62v5palijMdwr675HPgEuDqFMwih1DzRQ39HuzHto+3UbunlpV/WcnPX/45lVdV0uzrzdI2xzndW/Lg2AFc9dirOM6/XtqHr+ldKY0m1Irp7nvdfXuqhpEvK6ss2x8lQO2eWrZ9vI2yyrK0z3JO95Y8OG4Aq6re4+YlVVo5G1GjnmOa2RgzqzCziurq6sbcVdZa/ffV+6NMqt1Ty5p31kQyzzndEnFuVJyNqVHDdPdydy9x95L8/PzG3FXWGtp+KHlN8w74Wl7TPIrbFUc0URDnr8Yqzsakq7IxV9qvlLbN2+6PM69pHm2bt6W0X2mkc51dL86bFGfKhf5oETNbAfQGPjWzYne/IfxYktTs682ovKqSssoy1ryzhuJ2xZT2K03rhZ/DObtbS349biBTHl0HwL0/0AWhVDH39PxJV1JS4hUVFWnZl6TX83/ZwZRH11Fyamv+7bK+ivMYmNkz7l5y8Nd1KCuhndX1JOaNG8gzm7YzY/F69uzdF/VIGU9hSkqc2fUk5o0fyG83bWfmkirFGZLClJQ5o0tdnDMWK84wFKak1BldTuKh8YP4r9e3M11xNpjClJQ7vUsLHho/iP9WnA2mMKVRnN6lBWUTBvG7zduZ9rguCB0rhSmNZmjnFpSNH8SzW/6PGxXnMVGY0qiKE3E+pziPicKURndAnIsU59FQmJIWxZ2Dc87n3gji3K04j0hhStoUF9SPs1JxHoHClLQqLmjB/AmF/P6NHdywUHEejsKUtBtS8G3mTxzEH/6sOA9HYUokik6pi/NHCxTnwRSmRKbolG/z8MRBPP8XxXkwhSmRGpyI849v7uD6Ba/xxR7FCQpTYiCIs5AX3vyH4kxQmBILhZ1O5OGJhbz41j+4TnEqTImPwk4n8khpIWsUp8KUeBnUsS7Oa8tzN06FKbEzMBHn2r/+g2vLX83JOBWmxNLAjify6KRC1v51J9eWv8rne/ZGPVJaKUyJrQEdgjj/tPUDrit/LafiVJgSawM6nMgjpYP409YPuPY3uROnwpTYC+Is5KW/fcA1ORKnwpSMMKDDCTxSWsjLORKnwpSMMaDDCTw6KTfiVJiSUfq3D+J85W8fcPVjr/LP3dkZZ+gwzWyyma01sxfNrHcqhhI5kmSc697exdW/yc44Q4VpZicC1wBnAhOA/0jBTCJfqV8izlff3sVVWbhyhl0xBwN/cPfd7v4W0MLMdHgsadGv/Qk8Nnkwr/09++IMG9EJwK56r2uA45IvzGyMmVWYWUV1dXXIXYl8Wd92x/ObSUGcU7MozrBh7gKOr/e6GfBR8oW7l7t7ibuX5Ofnh9yVyKH1ScRZmUVxhg3zJeAsM2tqZp2Ane6ee3ccS+SyLc5QYbr7B8CvgReAx4DpqRhKpCH6tDue8slBnFMeXZfRcYa+UOPuv3L3Ie5+urtXpWIokYbqfXIQZ9U7H2Z0nLqCKlkniLMoo+NUmJKVTjv5OMonF7Hh3Y+Y/EjmxakwJWsFcQ5m47YgztovMidOhSlZ7dS29eJ89JWMiVNhStZLxrlp28dMeiQz4lSYkhOScW5+LzPiVJiSM+rHWfpwvONUmJJTeuUHcW7ZHsT52Rd7oh7pkBSm5Jz6cU56eF0s41SYkpN65R/HgslFsV05FabkrJ75zVkwuYg/b/8kdnEqTMlpPfObU56Ic+L8+MSpMCXn9cxvzoIpRbz5fg0T5r/Cp59HH6fCFAF6tGnOgimDeev9GibGIE6FKZLQvXUizh3Rx6kwRerp3ro5C6cURR6nwhQ5SLfW32LhlCL+uqOGCfNfpiaCOBWmyCF0a/0tFk4tYuuOT5kYQZwKU+Qwuraqi3NCWXrjVJgiR5CM8+2d6Y1TYYp8ha6tgnPOt3d+yvg0xakwRY5Cl0Sc/5uI85N/7m7U/SlMkaNUF+dnjR6nwhQ5Bl1afYtFUwfz9w9qGzVOhSlyjDq3rItzXNnLfNwIcSpMkQYI4izi3V21jHso9XEqTJEG6tyyGQunFLHtw9THqTBFQqgf5y1LNqRsu00b+hPN7CrgJmCvu3dP2UQiGaZzy2YsmlrE18xSts0wK+YTQM9UDSKSyQpOakbHFv+Ssu01eMV09/cBLIV/SohIoFHPMc1sjJlVmFlFdXV1Y+5KJKscccU0s2bAs4f41jx3n/dVG3f3cqAcoKSkxBs0oUgOOmKY7l4DFKVpFhFJaPChrJmNMrNngXZm9qyZDUzhXCI5LczFn+XA8hTOIiIJ5p6eUz8zewPY+hU/LB+I01UizXNkmufIjmaeUw51H0DawjwaZlbh7iVRz5GkeY5M8xxZmHl0S55IDMUtzPKoBziI5jkyzXNkDZ4nVoeyIhKI24opIihMkViKXZhmdpWZvZn465Uo55hsZmvN7EUz6x3xLN9MzPKhmV0e5SyJeXol/r/80cz+x8xOiXCWjma2xsyeN7PVUf9aJZlZVzPbbWYNunMudueYZtYS2AVsjOp9nmZ2IvA7gtsROwAPuvt5UcySmOdrwEnA1cAb7r4oqlkS87QEPnf3j8xsODDa3SdGNEtTYJ+77zOzc4Gp7h6HP7weA9oAc9z9T8f68xt8509jicnbyQYDf3D33cBbZtbCzJq4+74ohnH3vcD2uLzFLvlrlLAbiOx5de5ef9/NgaqoZkkys0JgO7C3oduI3aFsTJxAsGon1QDHRTRLbJlZHnAn8O8Rz9HXzNYC9wPPRTlLwhzgZ2E2EMmKGfbtZGmwCzi+3utmwEcRzRJLiUPIRcC97r4lylncfT0wxMz6Aw8AhVHNYmYjgXXuvjPMEU4kYWbA28leAu5K/OZrB+yM6jA2jiz4HTcf+K27r4h4lm+4++eJlx8Bn0U5D9AXONvMioHTgG5mNsrd3zuWjcTx4s8o4FpgCLAWmO3u6yKYYyowkeA84Tp3j/TcxcxWAL2BT4Hfu/sNEc5yIbAYeDnxpfXuPi2iWc4F7iD4dTJghru/FsUsBzOzh4EHGnLxJ3Zhiogu/ojEksIUiSGFKRJDClMkhhSmSAwpTJEYUpgiMfT/4FWDOrFajKAAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 256x256 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.figure(dpi=64,figsize=(4,4))\n",
    "\n",
    "plt.scatter(x_train[y_train==1][:,0],x_train[y_train==1][:,1],color='r') # 正例\n",
    "plt.scatter(x_train[y_train==-1][:,0],x_train[y_train==-1][:,1],color='g') # 正例\n",
    "\n",
    "x1 = np.arange(-1, 4, 0.1)\n",
    "x2 = (w[0] * x1 + b) / (-w[1])\n",
    "plt.plot(x1,x2)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. 对偶形式\n",
    "   "
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  },
  "vscode": {
   "interpreter": {
    "hash": "3c874ee3d65450ef899cacaa06bdca40f9e4450c5e631a94911db3215dbda5b8"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
